from typing import List

# 长度是 20000 的 case 超时了，真是疯狂
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        size = len(heights)
        if size <= 0:
            return 0
        result = [0] * (size * 2)
        arr = [0] + heights + [0]
        i = 1
        while i <= size:
            self.maxRect(i, arr, result, 0, size + 1)
            i += 1
        return max(result)

    def maxRect(self, i, arr, result, lb, up):
        h = arr[i]
        if h == 0:
            result[i] = 0
        elif result[i] > 0:
            pass
        else:
            idxs = [i]
            btm = i
            while btm > lb:
                if h <= arr[btm]:
                    if h == arr[btm]:
                        idxs.append(btm)
                    btm -= 1
                else:
                    break
            top = i
            while top < up:
                if h <= arr[top]:
                    if h == arr[top]:
                        idxs.append(top)
                    top += 1
                else:
                    break
            area = (top - btm - 1) * h
            for idx in idxs:
                result[idx] = area

solu = Solution()
print(solu.largestRectangleArea([2,1,5,6,2,3]))